//
//  Sort_11.swift
//  ArithmeticClass7
//
//  Created by xiangzuhua on 2020/10/13.
//  Copyright © 2020 xiang. All rights reserved.
//

import Foundation

public class Sort_11: NSObject {
    
    // 冒泡排序
    class func bubbleSort(_ arr: inout [Int]) {
        let n = arr.count
        if n <= 1 {//数组中无数据或者只有一个，则不需要排序
            return
        }
        
        for (index_i,_) in arr.enumerated() {
            var flag: Bool = false//无数据交换时，就不需要继续冒泡，
            for index_j in 0..<n - index_i - 1 {
                if arr[index_j] > arr[index_j + 1]{
                    let temp = arr[index_j]
                    arr[index_j] = arr[index_j + 1]
                    arr[index_j + 1] = temp
                    flag = true
                }
            }
            
            if !flag {
                break
            }
        }
    }
    
    // 插入排序
    class func insertionSort(_ arr: inout [Int]){
        let n = arr.count
        if n <= 1 {
            return
        }
        
        for i in 1..<n {
            let value = arr[i]
            var index = i - 1
            for j in stride(from: i - 1, to: -1, by: -1) {
                if value < arr[j] {
                    arr[j+1] = arr[j]
                    index = j
                } else {
                    break
                }
            }
            arr[index] = value
        }
    }
    
    // 选择排序
    class func selectSort(_ arr: inout [Int]){
        let n = arr.count
        if n <= 1 {
            return
        }
        for i in 0..<n {
            var temp: Int = arr[i]
            var minIndex = i
            for j in i + 1..<n {
                if arr[j] < temp {
                    temp = arr[j]
                    minIndex = j
                }
            }
            arr[minIndex] = arr[i]
            arr[i] = temp
        }
    }
    
    class func selectSort1(_ arr: inout [Int]){
        let n = arr.count
        if n <= 1 {
            return
        }
        for i in 0..<n {
            var temp: Int = arr[i]
            var minIndex = i
            for j in i+1..<n {
                if arr[j] < temp {
                    temp = arr[j]
                    minIndex = j
                }
            }
            arr[minIndex] = arr[i]
            arr[i] = temp
        }
        
    }
}
